package mo.tags.design;

import java.util.HashMap;
import java.util.Map;

class LRUCache {

    private final int capacity;
    private final Map<Integer, Node> key2node;
    private final Node head;
    private final Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        key2node = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        Node node = key2node.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = key2node.get(key);
        if (node != null) {
            node.value = value;
            moveToHead(node);
            return;
        }
        //超出容量
        if (key2node.size() == capacity) {
            Node removedNode = tail.pre;
            key2node.remove(removedNode.key);
            removedNode.pre.next = tail;
            tail.pre = removedNode.pre;
        }
        Node newNode = new Node(key, value);
        head.next.pre = newNode;
        newNode.next = head.next;
        head.next = newNode;
        newNode.pre = head;
        key2node.put(key, newNode);
    }


    private void moveToHead(Node node) {
        Node pre = node.pre;
        Node next = node.next;

        pre.next = next;
        next.pre = pre;

        Node headNext = head.next;
        node.next = headNext;
        node.pre = head;
        headNext.pre = node;
        head.next = node;
    }


    private static class Node {
        private int key;
        private int value;
        private Node pre;
        private Node next;

        public Node() {
        }

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }


    //["LRUCache","put","put","get","put","put","get"]
    //[[2],         [2,1],[2,2],[2],[1,1],[4,1],[2]]
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(2, 1);
        lruCache.put(2, 2);
        lruCache.get(2);
        lruCache.put(1, 1);
        lruCache.put(4, 1);
        lruCache.get(2);
    }
}